package main

import (
	"fmt"
	"sort"
)

//#link: https://leetcode-cn.com/problems/russian-doll-envelopes/
func main() {
	envelopes := [][]int{
		{5, 4},
		{6, 4},
		{6, 7},
		{2, 3},
	}
	fmt.Println(maxEnvelopes(envelopes))
}

func maxEnvelopes(envelopes [][]int) int {
	sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[i][1] > envelopes[j][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})
	top := make([]int, len(envelopes))
	pile := 0
	for _, num := range envelopes {
		left, right := 0, pile
		for left < right {
			mid := left + (right-left)>>1
			if num[1] > top[mid] {
				left = mid + 1
			} else if num[1] <= top[mid] {
				right = mid
			}
		}
		if left == pile {
			pile++
		}
		top[left] = num[1]
	}
	return pile
}
